package test;

public class LongestCommonSubsequence {
	public static void main(String[] args) {
		LongestCommonSubsequence t = new LongestCommonSubsequence();
		t.lcs();
	}

	private void LCSLength(char[] x, char[] y, int m, int n, int[][] c, int[][] b) {

		int i, j;

		for (i = 0; i <= m; i++)
			c[i][0] = 0;
		for (j = 1; j <= n; j++)
			c[0][j] = 0;
		for (i = 1; i <= m; i++)
		{
			for (j = 1; j <= n; j++)
			{
				if (x[i - 1] == y[j - 1])
				{
					c[i][j] = c[i - 1][j - 1] + 1;
					b[i][j] = 0;
				}
				else if (c[i - 1][j] >= c[i][j - 1])
				{
					c[i][j] = c[i - 1][j];
					b[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i][j - 1];
					b[i][j] = -1;
				}
			}
		}
	}

	void PrintLCS(int b[][], char[] x, int i, int j)
	{
		if (i == 0 || j == 0)
			return;
		if (b[i][j] == 0)
		{
			PrintLCS(b, x, i - 1, j - 1);
			System.out.println(x[i - 1]);
		}
		else if (b[i][j] == 1)
			PrintLCS(b, x, i - 1, j);
		else
			PrintLCS(b, x, i, j - 1);
	}

	private void printArray(int[][] src){
		
		for(int i=0;i<src.length;i++){
			for(int j=0;j<src[0].length;j++){
				System.out.print(src[i][j]+"\t");
			}
			System.out.print("\n");
		}
	}
	int lcs()
	{
		String str1 = "abcbdab";
		String str2 = "bdcaba";

		char[] x = str1.toCharArray();
		char[] y = str2.toCharArray();

		int m = x.length;
		int n = y.length;
		int b[][] = new int[m+1][n+1];
		int c[][] = new int[m+1][n+1];

		LCSLength(x, y, m, n, c, b);
		printArray(c);
		System.out.println("b:");
		printArray(b);
		PrintLCS(b, x, m, n);

		return 0;
	}
}